1919D - 01 Tree - CodeForces Solution

/*#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx")*/
#include <bits/stdc++.h>

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

using ll = long long;
using ld = long double;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
//#define endl '\n'
#define int ll
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pcc pair <char, char>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define in insert
#define MP make_pair
#define sz(s) (int)s.size()
#define inf (ll)1e18

//typedef tree<int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 5e5 + 10;
const int mod = 998244353;

int n;
vector <int> a, pr, nxt;

bool good(int x)
{
    if(x < 1 || x > n)
        return false;
    return a[pr[x]] == a[x] - 1 || a[nxt[x]] == a[x] - 1;
}

void solve()
{
    cin >> n;
    a = pr = nxt = vector <int> (n + 2, -2);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 0; i < n + 2; i++)
    {
        pr[i] = i - 1;
        nxt[i] = i + 1;
    }
    priority_queue <pii> pq;
    vector <int> u(n + 2, 0);
    for(int i = 1; i <= n; i++)
    {
        if(good(i))
        {
            pq.push({a[i], i});
            u[i] = 1;
        }
    }
    while(!pq.empty())
    {
        int x = pq.top().first, y = pq.top().second;
        pq.pop();
        pr[nxt[y]] = pr[y];
        nxt[pr[y]] = nxt[y];
        if(good(pr[y]) && u[pr[y]] == 0)
        {
            u[pr[y]] = 1;
            pq.push({a[pr[y]], pr[y]});
        }
        if(good(nxt[y]) && u[nxt[y]] == 0)
        {
            u[nxt[y]] = 1;
            pq.push({a[nxt[y]], nxt[y]});
        }
    }
    int cnt = 0, mn = inf;
    for(int i = 1; i <= n; i++)
    {
        mn = min(mn, a[i]);
        cnt += !u[i];
    }
    if(cnt == 1 && mn == 0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return;
}

signed main()
{
    //freopen("br1.in", "r", stdin);
    //freopen("br1.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    cin >> tc;
    while(tc--)
        solve();
    return 0;
}